Computers use resources, such as memory, modems and printers, during the execution of computer programs. Many of these resources are only used periodically by any given computer program. For example, the amount of time a word processing application requires a printer to print documents is typically small relative to the amount of time that the word processing application is used to create documents. If the only process that had access to the printer was a single word processing application, the printer would remain idle most of the time.
To take full advantage of resources, computer networks have been developed in which processes running on many computer devices or “nodes” can share resources. Thus, instead of having to purchase one printer for every computer, users may purchase a single printer that may be connected to a network that has many computers. Processes on each computer on the network access the printer only when the processes require the printer.
Even though resources may be shared, as described above, many resources may not be used by more than one process at any given time. For example, most printers are unable to print more than one document at a time. Other resources, such as data blocks of a storage medium or tables stored on a storage medium, may be concurrently accessed in some ways (e.g. read) by multiple processes, but accessed in other ways (e.g. written to) by only one process at a time. Consequently, mechanisms have been developed which control access to resources.
One such mechanism is referred to as a lock. A lock is a data structure that indicates that a particular process has been granted certain rights with respect to the resource. There are many types of locks. Some types of locks may be shared by many processes, while other types of locks prevent any other locks to be granted on the same resource.
Before a process can perform an operation on a resource, the process is required to obtain a lock that grants to the process the right to perform the desired operation on the resource. To obtain a lock, a process transmits a request for the lock to a lock manager. A lock manager is a process that is responsible for granting, queuing, and keeping track of locks on one or more resources. To manage the use of resources in a network system, lock managers are executed on one or more nodes in the network. The node that is executing the lock manager that governs access to a particular resource is referred to as the “master node”, or simply the “master”, of that resource.
According to one prior art implementation, a lock manager implements two types of objects: a resource object and a lock. Resource objects are data structures that correspond to actual resources. An application that uses a lock manager establishes a mapping between actual resources and resource objects. Each resource object has two queues: a granted queue and a convert queue. The granted queue is an unordered list of locks that have been granted. The convert queue is a partially ordered list of locks that have been requested, but not yet granted. Typically, a request for a lock is actually a convert request, where a process holding a lock is requesting that the lock it holds be converted from one mode of lock to a different mode of lock.
Locks are data structures that identify a process and a lock mode. Lock managers attach locks to the grant queues of resource objects to indicate that the process identified in the lock has been granted a lock of the type indicated in the lock on the resource that corresponds to the resource object to which the lock is attached.
FIG. 1 is a block diagram illustrating a typical lock manager 106. Lock manager 106 is a process that is configured to manage a resource object 100 stored in a memory 108. The resource object includes a granted queue 102 and a convert queue 104. Lock manager 106 has attached three locks 110, 112 and 114 to the granted queue 102, and one convert request 130 to the convert queue 104.
All locks and convert requests have a process ID portion and a lock mode portion. The process ID portion 116 of lock 110 indicates that a process PROC_1 owns lock 110, and the lock mode portion 118 of lock 110 indicates that lock 110 is an exclusive lock. The process ID portion 120 of lock 112 indicates that lock 112 is owned by a process PROC_2, and the lock mode portion 122 of lock 112 indicates that lock 112 is a NULL mode lock. The process ID portion 124 of lock 114 indicates that lock 114 is owned by a process PROC_3, and the lock mode portion 126 of lock 114 indicates that lock 114 is a NULL lock. The process ID portion 132 of convert request 130 indicates that convert request 130 is associated with process PROC_4, and the lock mode portion 136 of convert request 130 indicates that PROC_4 currently holds a NULL mode lock on the resource. In addition to a lock mode portion 136, convert request 130 has a requested mode portion 134 that indicates that PROC_4 is requesting an exclusive mode lock.
Lock manager 106 has attached locks 110, 112 and 114 to granted queue 102, indicating that PROC_1 currently has exclusive ownership of the resource that corresponds to resource object 100. Lock manager 106 has attached convert request 130 to the convert queue 104, indicating that PROC_4 has requested but has not yet been granted an exclusive mode lock on the resource associated with resource object 100.
The convert queue of a resource object is a partially ordered list that holds all outstanding (ungranted) lock requests. If any outstanding lock requests have not been granted, one of the ungranted lock requests will be at the “head” of the convert queue. Even if the currently granted locks do not prevent a lock manager from granting a particular lock request, the lock request is placed on the convert queue if the convert queue is not empty. This policy prevents “livelocks”, where one process cannot make progress in the system while other processes can.
In networked computer systems, some or all of the processes that are holding and requesting locks on a particular resource may be on different nodes than the master node of that resource. When the node that is executing a process that requests a lock on a resource is not the master node for the resource, a lock request must be transmitted between nodes. The computational power that must be expended to facilitate such inter-node messages is significant relative to the power required for intra-node communication. In addition, inter-node communication is generally slower than intra-node communication. Further, the inter-node traffic thus generated reduces the throughput available for other types of inter-node traffic, which may be significant when the inter-node traffic is between workstations on a network.
One technique for reducing the inter-node traffic related to lock operation involves spreading shadows of a resource object over many nodes, effectively turning the resource object into a distributed object. An implementation of this technique is described, for example, in U.S. Pat. No. 6,574,654, issued Jun. 3, 2003, the contents of which are incorporated herein by this reference.
By spreading shadows of the resource object over many nodes, the processing power of multi-processing systems may be exploited in that each of the nodes that has a shadow resource object may be used to perform lock operations related to the resource. Further, because the lock management workload for a resource is distributed, the processing load required to perform lock management for the resource is less likely to overburden a node than in lock management systems in which all lock operations for a resource must be performed at a single node.
Using the shadow resource object approach, the master resource object for a resource grants locks to shadow resource objects located on the nodes on which are located the processes that desire to access the resource. Each shadow resource object, in turn, grants locks on the resource to the processes that are located on the same node as the shadow resource object. The master resource object may also act as a shadow resource object to the processes running on the master node that require access to the resource owned by the master resource object.
The lock owned by each shadow resource object determines the types of locks the shadow resource object is allowed to grant to processes. If the lock owned by a shadow resource object does not give the shadow resource object the right to grant a lock requested by a process on the same node as the shadow resource object, then the shadow resource object may request for a lock upgrade from the master resource object.
Because the processes that use a resource do not have to communicate directly with the master resource object, the amount of inter-node traffic required by the distributed lock management system may be less than that required by lock management systems that employ a single centralized resource object for each resource. Specifically, inter-node traffic is avoided when the shadow resource object owns a lock that allows the shadow resource object to perform a requested lock operation without communicating with the master resource object.
When shadow lock objects are used, the lock information related to a single resource may be reflected on multiple nodes. For example, the same lock request may be reflected on both the local shadow resource object and the master resource object. In this case, the master node has “global knowledge” of the request. In other words, the master node knows which node made the lock request, and what lock mode was requested. In contrast, the local shadow resource object has “local knowledge” of the request. Specifically, the local resource object may identify which local process requested the lock, and what lock mode was requested by that process.
For any given resource, the information about the locks held and requested on the resource should be consistent across the cluster of nodes that access the resource, except for a small time interval when messages are in transit between the nodes. However, due to various reasons (such as missing messages, bugs, etc), there may be inconsistencies in enqueue lock information between the shadow and master nodes. Such inconsistencies are referred to herein as “lock-related inconsistencies”.
One example of a lock-related inconsistency is a situation in which the master resource object indicates that an exclusive lock has been granted to node A, but the shadow lock resource of node A indicates that node A is still waiting for the grant. As another example, a node B may be requesting an exclusive mode (“EX mode”) lock on a resource, but the master node may not have any knowledge of the request. Inconsistencies such as these may lead to a hang situation.
In a more serious case, two nodes may both “think” that they were granted exclusive mode to the same resource. This type of lock-related inconsistency may lead to corruption in the resource.
When lock-related inconsistencies are discovered, measures have to be taken to resolve the inconsistencies. In the context of a cluster of database servers, resolving lock-related inconsistencies typically involves performing some form of resource reconfiguration operation. Such reconfiguration operations may, for example, involve restarting the database server on one or more of the nodes in the cluster. Unfortunately, the process of restarting a database server can have a significant detrimental effect on the performance of the system.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.